package interview.dp;

import java.util.Arrays;

/**
 * 题目简述：给出n个正整数闭区间，每个区间有个价值v，求取k个不相交的区间的最大价值总和
 */
public class MaxIntervalValue {

    public static void main(String[] args) {
        System.out.println(new MaxIntervalValue().maxValue(new int[][]{{1, 4, 2}, {2, 4, 2}, {4, 5, 3}}, 2));
    }
    /**
     * 思路：动态规划。首先将区间按end升序排序，然后扫描记录每个区间i的前置区间编号pi（小于区间i的start的最大end区间）,
     * 区间从1开始编号，第一个区间的pi=0
     * 1. 定义dp：dp[i][j]为从前i个区间选j个的最大价值和
     * 2. 状态转移公式：dp[i][j]分为两种情况，故dp[i][j] = max(情况1，情况2)
     *      （1）不选第i个区间，dp[i][j] = dp[i-1][j]
     *      （2）选第i个区间，dp[i][j] = value[i] + dp[pi][j-1]
     * 3. 初始化：dp[i][0]=0; dp[0][j] = 0
     */
    int maxValue(int[][] inters, int k) {
        //inters元素格式：[start, end, value]
        //将区间按end升序排序
        Arrays.sort(inters, (in1, in2) -> in1[1] - in2[1]);
        //扫描记录每个区间i的前置区间编号pi
        int[] pi = new int[inters.length+1];
        for (int i = 1;i < inters.length;i++) {
            for (int j = i-1;j >= 0;j--) {
                //向前查找小于区间i的start的最大end区间
                if (inters[j][1] < inters[i][0]) {
                    pi[i+1] = j+1;
                    break;
                }
            }
        }
        //dp[i][j]为从前i个区间选j个的最大价值和
        int[][] dp = new int[inters.length + 1][k + 1];
        for (int i = 1;i <= inters.length;i++) {
            for (int j = 1;j <= k;j++) {
                dp[i][j] = Math.max(dp[i-1][j], inters[i-1][2] + dp[pi[i]][j-1]);
            }
        }
        return dp[inters.length][k];
    }
}
